package binary_tree.LeetCode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 二叉树的最大宽度
 */
public class Num_622widthOfBinaryTree {
    public int widthOfBinaryTree(TreeNode root) {
         if (root==null){
             return 0;
         }
        Deque<TreeNode> queue=new LinkedList<>();
         //根节点的编号为0
        root.val=0;
        int width=0;
        queue.offer(root);
        int levelsize=0;
        while(!queue.isEmpty()){
            levelsize=queue.size();
            //借用队头和队尾的差值表示宽度
            width=Math.max(width,queue.getLast().val-queue.getFirst().val+1);
            //一次处理一层，进入这个循环前队列中是一层的所有非空节点
            while (levelsize!=0){
                TreeNode temp=queue.poll();
                //子节点入队前修改val，val=满二叉树中节点编号
                if (temp.left!=null){
                    temp.left.val= temp.val*2+1;
                    queue.offer(temp.left);
                }
                if (temp.right!=null){
                    temp.right.val= temp.val*2+2;
                    queue.offer(temp.right);
                }
                levelsize--;
            }
        }
        return width;
    }
}
